package LeetCode;

import util.BinaryTreeUtil;
import util.TreeNode;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution257 {

    public static void main(String[] args) {
        Integer[] data = new Integer[]{1,2,3,null,5};
        TreeNode root = BinaryTreeUtil.build(1, data);
        List<String> strings = new Solution257().binaryTreePaths(root);
        System.out.println(strings);
    }


    // 用于存储遍历到的节点值
    List<Integer> cache = new ArrayList<>();

    // 用于存储结果
    List<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        helper(root);
        return res ;
    }

    private void helper(TreeNode root){

        if(root == null){
            return ;
        }

        cache.add(root.val);
        helper(root.left);
        helper(root.right);

        // 如果是叶子节点，生成一个字符串
        if(root.left == null && root.right == null){
            StringBuilder builder = new StringBuilder();
            // 遍历生成，并将最后一个节点数据从cache 中擦去
            Iterator<Integer> iterator = cache.iterator();
            while (iterator.hasNext()){
                builder.append(iterator.next());
                if (iterator.hasNext()){
                    builder.append("->");
                }
            }
            res.add(builder.toString());
        }

        cache.remove(cache.size()-1);
    }
}